package core;

/**
 * Solves finds the maximum flow through a SimpleGraph via the pre-flow push algorithm.
 * @author Michael Pitts
 */
public class PrePush {
	
	/** Gets a MaxFlowSolver that will use the Pre Flow Push algorithm.*/
	public static MaxFlowSolver getSolver() {
		return new MaxFlowSolver() {
			public double solve(SimpleGraph the_graph) {return PrePush.solve(the_graph);}
			public String getName() {return "Preflow Push";}
		};
	}

	/**
	 * Solves the max flow problem using the Pre Flow Push algorithm.
	 * @param the_graph is the graph to solve on.
	 * @return the maximum possible flow.
	 */
	public static int solve(final SimpleGraph the_graph) {
		final PrePushData data = new PrePushData(the_graph);
		runPrePushAlgorithm(data, the_graph);
		return data.getNetFlow();
	}

	/**
	 * Runs the Pre Flow Push algorithm.
	 * @param graph_data is the data for the graph, such as flow and excess.
	 * @param the_graph is the graph the algorithm will run on.
	 */
	public static void runPrePushAlgorithm(final PrePushData graph_data, 
			final SimpleGraph the_graph) {
		Vertex v, w;
		Edge e;
		while (graph_data.hasExcessNodes()) {
			v = graph_data.getExcessNode();
			while(graph_data.hasNextEdgeAndExcess(v)) {
				e = graph_data.nextEdge(v);
				w = the_graph.opposite(v, e);
				if (graph_data.getHeight(w) < graph_data.getHeight(v)) 
					push(v, w, e, graph_data);
			}
			graph_data.resetEdge(v);
			if (graph_data.getExcess(v) > 0) graph_data.increaseHeight(v);
		}
	}

	/**
	 * Pushes excess flow from one Vertex to another.
	 * @param v is the Vertex with excess.
	 * @param w is the Vertex that will get some of the excess.
	 * @param e is the edge connecting v and w.
	 * @param map is the NodeData that stores the flow information.
	 * @return true if the change in flow was non-zero.
	 */
	public static boolean push(final Vertex v, final Vertex w, final Edge e, 
			final PrePushData map) {
		double delta;
		if (v.equals(e.getFirstEndpoint())) { // forward edge
			delta = Math.min(map.getExcess(v), ((Double)e.getData()) - map.get(e));
			map.change(e, delta);
			map.changeExcess(v, -delta);
			map.changeExcess(w, +delta);
		} else { // reverse edge
			delta = Math.min(map.getExcess(v), map.get(e));
			map.change(e, -delta);
			map.changeExcess(v, -delta);
			map.changeExcess(w, delta);
		}
		return delta != 0;
	}
}
